package linkedlist;

/**
 * @author tongchen
 * @create 2023-03-03 22:58
 */
public class LinkedListTest {
    public static void main(String[] args) {


    }

}
class LinkedList{
    public LinkedList() {
    }
    //用来计数操作
    private static int counts;
    //设置根结点，往后的任何对链表操作的方法都是利用根结点进行操作的
    Node root;

    public LinkedList(Node root) {
        this.root = root;
    }

    // 1、无头单向非循环链表实现
    //头插法
    //无需考虑特殊情况：即使头结点是空，也并不影响我们的插入操作
    public void addFirst(int data){
        //创建新的结点
        Node node = new Node(data);
        node.next=root;
        root=node;
    }
    //尾插法
    /*
    和头插法有所不同的是：尾插法是将元素插入到链表末尾，必须考虑前一个元素的存在性，同时链表不能立即插入
     */
    public void addLast(int data){
        //创建新的元素
        Node node = new Node(data);
        //判断root的存在性
        if(root==null){
            root=node;
            return;
        }
        //确定头结点的存在之后，利用前一个节点向后一个节点插入元素
        Node cur=root;
        while(cur.next!=null){
            cur=cur.next;
        }
        //遍历到最后一个元素
        cur.next=node;
        //操作结束
    }

    //根据下标数据进行插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        //判断index的合法性
        if(index<0||index>size()){
            throw new RuntimeException("index无效");
        }

        //排除特殊情况，如果是插入到第一个元素和最后一个元素，直接利用头插和尾插进行操作
        if(index==0){
            addFirst(data);
        }
        else if(index==size()){
            addLast(data);
        }
        //其他情况
        else {

            //创建新的结点
            Node node = new Node(data);
            Node cur=new Node(data);
            //遍历找位置插入：例如如果在第一个位置插入的话，那就直接插入即可，不用循环
            for (int i = 0; i <index-1 ; i++) {
                cur=cur.next;
            }
            //交接结点
          cur.next=node.next;
            node.next=cur;

        }

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        //首先判断链表的有效性
        if(root==null){
            throw new RuntimeException("当前链表为空");
        }
        //循环遍历即可
        //创建中间结点
        Node cur=root;
        while (cur.next!=null){
            if(cur.value==key){
                return true;
            }
            cur=cur.next;
        }
       return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        //确认链表的存在性
        if(root==null){
            throw new RuntimeException("当亲链表为空");
        }
        //创建当前指针来遍历
        Node cur=root;
        //定义前驱结点
        Node pre=null;

        while (cur!=null){

        }

    }
    //得到单链表的长度
    public int size(){

       return 0;
    }
    public void clear() {

    }
    public void display() {


    }
    //设置查找方法
    //需要注意的是：在查找完成之后，后面进行在特定位置添加操作时，需要分三种情况进行讨论（1.在最后一个位置2.在中间位置3.链表还没有达到该位置 ）
    public int find(int value){
        return 0;
    }


}
class Node{
    int value;
    //用来定义序号
    int num;
    Node next;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +'}';
    }
}